package cn.edu.jxau.test;

import java.util.Arrays;

/**
 * 利用Kosaraju算法计算有向图的强连通分量
 * 
 * @author 付大石
 */
public class KosarajuSCC {

    public static void main(String[] args) {

        DirectedGraph g = new DirectedGraph(13);
        g.addEdge(4, 2);
        g.addEdge(2, 3);
        g.addEdge(3, 2);
        g.addEdge(6, 0);
        g.addEdge(0, 1);
        g.addEdge(2, 0);
        g.addEdge(11, 12);
        g.addEdge(12, 9);
        g.addEdge(9, 10);
        g.addEdge(9, 11);
        g.addEdge(8, 9);
        g.addEdge(10, 12);
        g.addEdge(11, 4);
        g.addEdge(4, 3);
        g.addEdge(3, 5);
        g.addEdge(7, 8);
        g.addEdge(8, 7);
        g.addEdge(5, 4);
        g.addEdge(0, 5);
        g.addEdge(6, 4);
        g.addEdge(6, 9);
        g.addEdge(7, 6);
        System.out.println(new KosarajuSCC(g).count());
    }

    /**
     * 标记
     */
    private boolean[] marked;

    /**
     * 强连通分量id
     */
    private int[] id;

    /**
     * 强连通分量个数
     */
    private int count;

    public KosarajuSCC(DirectedGraph g) {

        marked = new boolean[g.v()];
        id = new int[g.v()];
        Iterable<Integer> order = new DirectedDFSOrder(g).reversePost();
        DirectedGraph rg = g.reverse();
        for (int v : order) {
            if (!marked[v]) {
                dfs(rg, v);
                count++;
            }
        }
    }

    private void dfs(DirectedGraph g, int v) {

        marked[v] = true;
        id[v] = count;
        for (int w : g.adj(v)) {
            if (!marked[w]) {
                dfs(g, w);
            }
        }
    }

    public boolean connected(int v, int w) {
        return id[v] == id[w];
    }

    public int id(int v) {
        return id[v];
    }

    public int count() {
        System.out.println(Arrays.toString(id));
        return count;
    }
}
